/*
 * @Author: zxc
 * @Date: 2020-08-16 09:00:12
 * @LastEditTime: 2020-08-16 09:38:02
 * @LastEditors: zxc
 * @Description: 希尔排序
 */
import { swap } from "../utils";
// 希尔排序，自组采用直接插入排序 针对有序序列在插入时采用交换法
export function shellSort(arr) {
  if (arr.length <= 1) return;
  // gap 是步长，每次右移一位，大概就是折半处理，直到步长为1
  for (let gap = arr.length >> 1; gap > 0; gap >>= 1) {
    // 下面是一个插入排序，排序的时候会按照步长gap就行数据选
    for (let i = gap; i < arr.length; i++) {
      let j = i - gap;
      for (j; j >= 0 && arr[j] > arr[i]; j -= gap) {
        swap(arr,j+gap,j)
      }
    }
  }
  return arr;
}


let arr = [34, 23, 42, 12, 52, 234, 5, 21];
console.log(shellSort(arr));
